from LeetCoder import *


class Solution:
    def extractMantra(self, matrix: List[str], mantra: str) -> int:
        arr = matrix
        m, n = len(arr), len(arr[0])
        h = [False] * 26

        def c2i(c):
            return ord(c) - ord('a')

        cp = [[] for _ in range(26)]

        for i in range(m):
            for j in range(n):
                num = matrix[i][j]
                c = c2i(num)
                h[c] = True
                cp[c].append((i, j))
        for num in mantra:
            if h[c2i(num)] == False:
                return -1
        q = [(0, 0, 0, 0)]  # cost0,x,y,i
        k = len(mantra)
        record = [[inf] * k for _ in range(m * n)]
        heapify(q)
        while q:
            cur = heappop(q)
            c, i, x, y = cur
            tmp = x * n + y
            if i == len(mantra):
                return c
            ls = cp[c2i(mantra[i])]
            for nx, ny in ls:
                cc = abs(nx - x) + abs(ny - y) + 1 + c
                tmp = nx * n + ny
                if cc < record[tmp][i]:
                    # record[i] = cc
                    record[tmp][i] = cc
                    heappush(q, (cc,  i + 1, nx, ny,))

        return -1


s = Solution()
print(s.extractMantra(["aaknqmyqifgv", "dlwayfyomlta", "dgzxmkwwvjru", "yxwaxfsqrfvj", "pbgwirqrgunu", "aafaxkjjolpi",
      "lbinkhqnxabr", "ikuwecqhmmzd", "tzraxzeeaxuk", "lxutzbqlweye", "daydrducohyc", "nmahtpcvcgcy"], "kujnpuqpyzoeekgccnzhtfrrlhu"))
print(s.extractMantra(matrix=["sd", "ep"], mantra="speed"))
print(s.extractMantra(matrix=["abc", "daf", "geg"], mantra="sad"))


class Solution:
    def extractMantra(self, matrix: List[str], mantra: str) -> int:
        arr = matrix
        m, n = len(arr), len(arr[0])
        h = [False] * 26

        def c2i(c):
            return ord(c) - ord('a')

        cp = [[] for _ in range(26)]

        for i in range(m):
            for j in range(n):
                num = matrix[i][j]
                c = c2i(num)
                h[c] = True
                cp[c].append((i, j))
        for num in mantra:
            if h[c2i(num)] == False:
                return -1
        q = [(0, 0, 0, 0)]  # cost0,x,y,i
        k = len(mantra)
        record = [[inf] * k for _ in range(m * n)]
        heapify(q)
        while q:
            cur = heappop(q)
            c, x, y, i = cur
            tmp = x * n + y
            if i == len(mantra):
                return c
            if c >= record[tmp][i]:
                continue
            if matrix[x][y] == mantra[i]:
                heappush(q, (c + 1, x, y, i + 1))
                continue
            ls = cp[c2i(mantra[i])]
            for nx, ny in ls:
                cc = abs(nx - x) + abs(ny - y) + 1 + c
                tmp = nx * n + ny
                if cc < record[tmp][i]:
                    # record[i] = cc
                    record[tmp][i] = cc
                    heappush(q, (cc, nx, ny, i + 1))

        return -1
